package com.wuxuan.algorithm_homework.hashAndWindow;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * -----------------------------------滑动窗口-------------------------------------------------------
 * <p>
 * 滑动窗口是一种在数组或字符串处理中常用的算法技巧，常用于解决区间类的问题。
 * 它通过维护一个可以在数据序列上滑动的窗口，在遍历数据的过程中动态调整窗口的大小和位置，从而高效地解决许多与子数组、子字符串相关的问题。
 * <p>
 * 基本原理
 * 滑动窗口算法的核心思想是利用双指针来维护一个窗口，这个窗口可以在数组或字符串上移动。通常使用两个指针，一个指向窗口的起始位置(左指针)，另一个指向窗口的结束位置(右指针)。
 * 通过移动这两个指针，动态地调整窗口的大小和位置，从而满足特定的条件，
 * 在遍历数据的过程中，右指针不断向右移动，扩大窗口，将新的元素纳入窗口中:
 * 当窗口内的元素不满足特定条件时，左指针向右移动，缩小窗口，移除窗口左侧的元素，直到窗口内的元素重新满足条件。
 * 通过这种方式，我们可以在一次遍历中完成对所有可能的子数组或子字符串的检查，从而将时间复杂度优化到 O(n)。
 */
public class Window {

    /**
     * 1.最长不重复的子数组 longestSubarray(subarray:子数组)
     * 示例 1:
     * 输入:[1，2，6，3，2，4，7]输出:[6,3,2,4,7]
     * <p>
     * <p>
     * 初始化：
     * 我们需要一个集合（Set），用来存储当前窗口里的数字。
     * 我们还需要两个指针，start 和 end，来记录当前最长的不重复子数组的起始和结束位置。
     * 还有一个指针 curStart，用来记录当前窗口的起始位置。
     * <p>
     * 滑动窗口：
     * 我们从数组的第二个数字开始（i = 1），逐个检查每个数字。
     * 每次检查时，我们看这个数字是否已经在窗口里（即 set 里）。
     * <p>
     * 处理重复数字：
     * 如果当前数字已经在窗口里，说明当前窗口不能再扩大了。我们需要移动窗口的左边界（curStart），直到这个重复的数字被移出窗口。
     * 每次移出一个数字，就从 set 里删除它。
     * <p>
     * 更新最长子数组：
     * 每次移动窗口后，我们检查当前窗口的长度（i - curStart）。
     * 如果当前窗口的长度比之前记录的最长子数组还要长，我们就更新 start 和 end，记录下当前窗口的起始和结束位置。
     * <p>
     * 返回结果：
     * 最后，我们根据 start 和 end，从原数组中提取出最长的不重复子数组。
     *
     * @param arr
     * @return
     */
    public int[] q1(int[] arr) {
        // 如果数组为空，直接返回空数组
        if (arr == null || arr.length == 0) {
            return arr;
        }

        // 初始化滑动窗口的左边界和右边界
        int start = 0;
        int end = 0;
        int curStart = 0;

        // 用一个集合来存储当前窗口里的数字
        Set<Integer> set = new HashSet<>();
        // 先把第一个数字加入窗口
        set.add(arr[0]);

        // 从第二个数字开始检查
        for (int i = 1; i < arr.length; i++) {
            // 如果当前数字已经在窗口里
            while (set.contains(arr[i])) {
                // 移动窗口的左边界，直到这个重复的数字被移出窗口
                set.remove(arr[curStart]);
                curStart++;
            }

            // 把当前数字加入窗口
            set.add(arr[i]);

            // 检查当前窗口的长度，更新最长子数组的起始和结束位置
            if (i - curStart > end - start) {
                start = curStart;
                end = i;
            }
        }

        // 返回最长的不重复子数组
        return Arrays.copyOfRange(arr, start, end + 1);
    }

    /**
     * 2.最小交换次数来组合所有的 1 (minSwaps)
     * 给定一个数组只含 0和 1，返回最小的 0,1 交换次数，让所有的 1 都连续。示例 1:
     * 输入:[1 10 110 0,1]
     * 输出:1
     * 解释:只需将数组中的第三个数 0和 最后一个数1交换位置，所有的1都连续排列
     * 示例 2:
     * 输入:[0,0,1]
     * 输出:0
     * 解释:数组中所有的1已经连续排列，不需要进行交换
     *
     * @param arr
     * @return
     */
    public int q2(int arr[]) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        //看传入的数组中有多少个1，判断滑动窗口的大小x
        int count = 0;
        for (int num : arr) {
            if (num == 1) {
                count++;
            }
        }

        //将问题转化为 长度为x的子串中，0最少多少个(几个0就需要和1交换几次才能连续)
        int minSwaps = Integer.MAX_VALUE;
        int zerosInWindow = 0;
        int left = 0;

        for (int right = 0; right < arr.length; right++) {
            // 统计窗口内0的数量
            if (arr[right] == 0) {
                zerosInWindow++;
            }

            //当窗口大小达到count时，开始判断是否更新最小交换次数
            if (right - left + 1 == count) {
                minSwaps = Math.min(minSwaps, zerosInWindow);
                //移动左边界，更新窗口中0的数量
                if (arr[left] == 0) {
                    zerosInWindow--;
                }
                left++;
            }
        }

        return minSwaps == Integer.MAX_VALUE ? 0 : minSwaps;
    }


    /**
     * 3.最小覆盖子串(minWindow)
     * 给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t所有字符的最小子串。如果 s 中不存在涵盖 t所有字符的子串，则返回空字符串""注意:
     * ·对于 t中重复字符，我们寻找的子字符串中该字符数量必须不少于 t中该字符数量。
     * 如果 s中存在这样的子串，我们保证它是唯一的答案。。
     * 示例 1:
     * 输入:S="ADOBECODEBANC",t="ABC"
     * 输出:"BANC”
     * 解释:最小覆盖子串“BANC"包含来自字符串 t 的 'A'、'B' 和'C'.
     * 示例 2:
     * 输入:s ="a",t="a"
     * 输出:"a"
     * 解释:整个字符串s是最小覆盖子串。
     * 示例 3:
     * 输入:s="a",t="aa"
     * 输出:""
     * 解释:t 中两个字符'a'均应包含在s的子串中,因此没有符合条件的子字符串，返回空字符串。
     *
     * @param s
     * @param t
     * @return
     */
    public String q3(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        //统计t中每个字符出现次数
        Map<Character, Integer> targetMap = countCharacter(t);

        //滑动窗口中的字符出现次数
        Map<Character, Integer> windowMap = new HashMap<>();
        //窗口左边界
        int l = 0;
        //最小窗口长度
        int minLength = Integer.MAX_VALUE;
        //当前窗口中已经满足的字符个数
        int count = 0;
        //最小窗口的起始位置
        int minLeft = 0;

        //cur先移动到某个地方，出现map中含有的字符，将左边界和有边界定义为此地方，然后再继续移动右边界寻找
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (targetMap.containsKey(c)) {
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

                //如果当前字符出现次数不超过目标字符串中该字符的次数，则计数器加一
                if (windowMap.get(c) <= targetMap.get(c)) {
                    count++;
                }
            }

            // 当窗口中包含了所有目标字符，尝试缩小窗口
            while (count == t.length()) {
                if (i - l +1 < minLength) {
                    minLength = i - l + 1;
                    minLeft = l;
                }
                char leftChar = s.charAt(l);
                if (targetMap.containsKey(leftChar)) {
                    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                    //如果当前字符出现次数小于目标字符串中该字符的次数，则计数器减一
                    if (windowMap.get(leftChar) < targetMap.get(leftChar)) {
                        count--;
                    }
                }
                //移动窗口左边界
                l++;
            }
        }
        //如果未找到符合条件的窗口，返回空字符串
        if (minLength > s.length()) {
            return "";
        }

        //返回最小覆盖子串
        return s.substring(minLeft, minLeft + minLength);
    }

    /**
     * 统计t中每个字符出现次数
     *
     * @param t
     * @return
     */
    private Map<Character, Integer> countCharacter(String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            if (!map.containsKey(t.charAt(i))) {
                //如果map中还没有当前字符，则存入此字符，定义次数为1
                map.put(t.charAt(i), 1);
            } else {
                //如果map中有当前字符，则获取次数，存入次数加一
                map.put(t.charAt(i), map.get(t.charAt(i)) + 1);
            }
        }
        return map;
    }

    @Test
    public void TestcCountCharacter() {
        Map<Character, Integer> m = countCharacter("abcdefaac");
        m.forEach((k, v) -> System.out.println(k + ":" + v));
    }


    @Test
    public void TestQ1() {
        Window w = new Window();

        //  1.最长不重复的子数组
        //  示例 1:
        //  输入:[1，2，6，3，2，4，7]输出:[6,3,2,4,7]
        int[] arr1 = {1, 2, 6, 3, 2, 4, 7};
        int[] result1 = w.q1(arr1);
        System.out.println(Arrays.toString(result1));

    }

    @Test
    public void TestQ2() {
        Window w = new Window();

        //2.最小交换次数来组合所有的 1
        //示例 1:
        //输入:[1, 1, 0, 1, 1, 0, 0, 1]
        //输出:1
        int[] arr21 = {1, 1, 0, 1, 1, 0, 0, 1};
        int result21 = w.q2(arr21);
        System.out.println(result21);
        //示例 2:
        //输入:[0,0,1]
        //输出:0
        int[] arr22 = {0, 0, 1};
        int result22 = w.q2(arr22);
        System.out.println(result22);

    }

    @Test
    public void TestQ3() {
        Window w = new Window();

        //3.最小覆盖子串
        //示例 1:
        //输入:S="ADOBECODEBANC",t="ABC"
        //输出:"BANC”
        String s1 = w.q3("ADOBECODEBANC", "ABC");
        System.out.println(s1);

        //示例 2:
        //输入:s ="a",t="a"
        //输出:"a"
        String s2 = w.q3("a", "a");
        System.out.println(s2);

        //示例 3:
        //输入:s="a",t="aa"
        //输出:""
        String s3 = w.q3("a", "aa");
        System.out.println(s3);
    }

}
